package cn.tedu.sort;

import org.junit.Test;

public class QuickSort extends BasicSort {

    private int partition(Comparable[] arr, int lo, int hi) {
        // 将数组切分为arr[lo..i-1], arr[i], arr[i+1..hi]
        int i = lo, j = hi + 1; // 左右扫描指针
        Comparable v = arr[lo]; // 切分元素
        while (true) {
            // 扫描左右，检查扫描是否结束并交换元素
            while (less(arr[++i], v))
                if (i == hi)
                    break;
            while (less(v, arr[--j]))
                if (j == lo)
                    break;
            if (i >= j)
                break;
            exch(arr, i, j);
        }
        exch(arr, lo, j); // 将v = arr[j]放入正确的位置
        return j; // arr[lo..j-1] <= a[j] <= a[j+1..hi] 达成
    }

    @Override
    protected void sort(Comparable[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    protected void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo)
            return;
        int j = partition(arr, lo, hi); // 切分
        sort(arr, lo, j - 1); // 将左半部分arr[lo..j-1]排序
        sort(arr, j + 1, hi); // 将右半部分arr[j+1..hi]排序
    }

    @Test
    public void test() {
        generateNumbers();
        sort(numbers);
        show();
    }
}
